// https://leetcode.cn/problems/design-add-and-search-words-data-structure/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用字典树(Trie)结构存储单词
// 2. 支持添加单词和带通配符'.'的搜索功能
// 3. 遇到普通字符按路径搜索，遇到'.'时遍历所有子节点
// 4. 递归实现通配符匹配，深度优先搜索所有可能路径
// 5. 时间复杂度：添加O(L)，搜索最坏O(26^L)

// 本题主函数由AI生成

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

struct TrieNode
{
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class WordDictionary 
{
private:
    TrieNode* root;
public:
    WordDictionary() 
    {
        root = new TrieNode();
    }

    ~WordDictionary() 
    {
        destroyTrie(root);
    }
    
    void addWord(string word) 
    {
        TrieNode* cur = root;

        for (const char& ch : word) 
        {
            int index = ch - 'a';
            if (cur->children[index] == nullptr) 
            {
                cur->children[index] = new TrieNode();
            }
            cur = cur->children[index];
        }

        cur->isEnd = true;
    }
    
    bool search(string word) 
    {
        return searchHelper(word, 0, root);
    }
private:
    WordDictionary(const WordDictionary&) = delete;
    WordDictionary& operator=(const WordDictionary&) = delete;

    bool searchHelper(const string& word, int index, TrieNode* node) 
    {
        if (index == word.size()) 
        {
            return node != nullptr && node->isEnd;
        }
        
        char ch = word[index]; 
        if (ch != '.') 
        {
      
            int childIndex = ch - 'a';
            if (node->children[childIndex] == nullptr) 
            {
                return false;
            }
            return searchHelper(word, index + 1, node->children[childIndex]);
        } 
        else 
        {
            for (int i = 0; i < 26; i++) 
            {
                if (node->children[i] != nullptr) 
                {
                    if (searchHelper(word, index + 1, node->children[i])) 
                    {
                        return true;
                    }
                }
            }
            return false;
        }
    }

    void destroyTrie(TrieNode* node) 
    {
        if (node == nullptr) 
        {
            return;
        }

        for (int i = 0; i < 26; i++) 
        {
            destroyTrie(node->children[i]);
        }

        delete node;
    }
};

int main() 
{
    WordDictionary wordDict;
    
    cout << "=== 测试1: 基本功能 ===" << endl;
    wordDict.addWord("bad");
    wordDict.addWord("dad");
    wordDict.addWord("mad");
    
    cout << "搜索 'pad': " << (wordDict.search("pad") ? "true" : "false") << endl;      // 预期: false
    cout << "搜索 'bad': " << (wordDict.search("bad") ? "true" : "false") << endl;      // 预期: true
    cout << "搜索 '.ad': " << (wordDict.search(".ad") ? "true" : "false") << endl;      // 预期: true
    cout << "搜索 'b..': " << (wordDict.search("b..") ? "true" : "false") << endl;      // 预期: true
    cout << "搜索 '...': " << (wordDict.search("...") ? "true" : "false") << endl;      // 预期: true
    cout << "搜索 '....': " << (wordDict.search("....") ? "true" : "false") << endl;    // 预期: false
    
    cout << "\n=== 测试2: 边界情况 ===" << endl;
    WordDictionary wordDict2;
    
    // 测试空字符串
    wordDict2.addWord("");
    cout << "搜索空字符串: " << (wordDict2.search("") ? "true" : "false") << endl;      // 预期: true
    cout << "搜索 '.': " << (wordDict2.search(".") ? "true" : "false") << endl;         // 预期: false
    
    cout << "\n=== 测试3: 复杂通配符 ===" << endl;
    WordDictionary wordDict3;
    
    wordDict3.addWord("abc");
    wordDict3.addWord("abd");
    wordDict3.addWord("acc");
    wordDict3.addWord("xyz");
    
    cout << "搜索 'ab.': " << (wordDict3.search("ab.") ? "true" : "false") << endl;     // 预期: true
    cout << "搜索 'a.c': " << (wordDict3.search("a.c") ? "true" : "false") << endl;     // 预期: true
    cout << "搜索 '..c': " << (wordDict3.search("..c") ? "true" : "false") << endl;     // 预期: true
    cout << "搜索 'x.z': " << (wordDict3.search("x.z") ? "true" : "false") << endl;     // 预期: true
    
    cout << "\n=== 测试4: 性能测试（长单词）===" << endl;
    WordDictionary wordDict4;
    
    wordDict4.addWord("abcdefghij");
    wordDict4.addWord("klmnopqrst");
    
    cout << "搜索 'abcdefghij': " << (wordDict4.search("abcdefghij") ? "true" : "false") << endl;    // 预期: true
    cout << "搜索 'a.c.e.g.i.': " << (wordDict4.search("a.c.e.g.i.") ? "true" : "false") << endl;    // 预期: true
    cout << "搜索 'klmnopqrst': " << (wordDict4.search("klmnopqrst") ? "true" : "false") << endl;    // 预期: true
    cout << "搜索 'k.m.o.q.s.': " << (wordDict4.search("k.m.o.q.s.") ? "true" : "false") << endl;    // 预期: true
    
    cout << "\n=== 所有测试完成 ===" << endl;
    
    return 0;
}